using Edge = struct Edge{
    int u,v,d;
};

bool cmp(const Edge&e1, const Edge&e2){
    return e1.d < e2.d;
}

const int maxn = 100005;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
     * @param cost int整型vector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */
    Edge e[maxn];

    int fa[maxn];
    int rank[maxn];
    void init(int V){
        for(int i = 0; i <= V; i++) {
            fa[i] = i;
            rank[i] = 0;
        }
    }
    int finds(int x)
    {
        if (x == fa[x]) return x;
        else return fa[x]=finds(fa[x]);
    }
    void unions(int x, int y){
        x = finds(x);
        y = finds(y);
        if (x == y) return;
        if (rank[x] < rank[y]){
            fa[x] = y;
        } else {
            fa[y] = x;
            if (rank[x] == rank[y]) rank[x]++;
        }
    }
    bool same(int x, int y){
        return finds(x) == finds(y);
    }
    int krusal(int V, int E)
    {
        sort(e, e+E, cmp);  //按cost从小到达排序
        init(V);
        int res = 0;
        for(int i = 0; i < E; i++){
            Edge tmp = e[i];
            if (!same(tmp.u, tmp.v)){
                unions(tmp.u, tmp.v);
                res += tmp.d;
            }
        }
        return res;
    }

    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        for(int i = 0; i < m; i++){
            e[i].u = cost[i][0];
            e[i].v = cost[i][1];
            e[i].d = cost[i][2];
        }
        return krusal(n, m);
    }
};